package 力扣;

/**
 * @Classname Test
 * @Description TODO
 * @Date 2021/2/20 19:43
 * @Created by xiaok
 */

import java.util.ArrayList;

/**
 *  * 判断一个点，是否在一个多边形区域内
 *  /**
 *  第二题 给你一些平面上的点组成的电子围栏，再给你一个点，怎么算它是不是被这些点包围
 *  Sample 1:
 *  输入：points = [[0,0],[0,1],[1,1],[1,0]]  point=[0.5,0.5]
 *  输出：true
 *
 *  Sample 2:
 *  输入：points = [[0,0],[0,1],[1,1],[1,0]]  point=[1.5,0.5]
 *  输出：false
 *
 *  Sample 3:
 *  输入：points = [[0,0],[1,1],[2,0.5],[3,1],[4,0]]  point=[2,0.75]
 *  输出：false
 *
 *  Notes：
 *  1. 程序里面一个类要实现这个方法，用main程序测试
 *  public boolean contains(List<double[]> points, double[] point){}
 *  2. 不能使用任何java.util.*; java.lang.*; 以外的包
 *
 *  * @Date 2021/2/21 12:19
 *  * @Created by xiaok
 *
 */
public class _第二题 {


    public static void main(String[] args) {
        double px = 2;
        double py = 0.75;
        ArrayList<Double> polygonXA = new ArrayList<Double>();
        ArrayList<Double> polygonYA = new ArrayList<Double>();
        polygonXA.add(0.0);
        polygonXA.add(1.0);
        polygonXA.add(2.0);
        polygonXA.add(3.0);
        polygonXA.add(4.0);

        polygonYA.add(0.0);
        polygonYA.add(1.0);
        polygonYA.add(0.5);
        polygonYA.add(1.0);
        polygonYA.add(0.0);
       /* double px = 113.705835;
        double py = 34.787479;
        ArrayList<Double> polygonXA = new ArrayList<Double>();
        ArrayList<Double> polygonYA = new ArrayList<Double>();
        polygonXA.add(113.700213);// 北京  
        polygonXA.add(113.706651);// 石家庄  
        polygonXA.add(113.706608);// 德州  
        polygonXA.add(113.707337);// 天津  
        polygonXA.add(113.701587);// 烟台  
        polygonXA.add(113.700128);// 唐山jdal  

        polygonYA.add(34.791532);
        polygonYA.add(34.791568);
        polygonYA.add(34.789242);
        polygonYA.add(34.786633);
        polygonYA.add(34.786669);
        polygonYA.add(34.789242);*/

        _第二题 test = new _第二题();
        System.out.println(test.isPointInPolygon(px, py, polygonXA, polygonYA));
    }


    public boolean isPointInPolygon(double px, double py, ArrayList<Double> polygonXA, ArrayList<Double> polygonYA) {
        boolean isInside = false;
        double ESP = 1e-9;
        int count = 0;
        double linePoint1x;
        double linePoint1y;
        double linePoint2x = 180;
        double linePoint2y;

        linePoint1x = px;
        linePoint1y = py;
        linePoint2y = py;

        for (int i = 0; i < polygonXA.size() - 1; i++) {
            double cx1 = polygonXA.get(i);
            double cy1 = polygonYA.get(i);
            double cx2 = polygonXA.get(i + 1);
            double cy2 = polygonYA.get(i + 1);
            if (isPointOnLine(px, py, cx1, cy1, cx2, cy2)) {
                return true;
            }
            if (Math.abs(cy2 - cy1) < ESP) {
                continue;
            }

            if (isPointOnLine(cx1, cy1, linePoint1x, linePoint1y, linePoint2x, linePoint2y)) {
                if (cy1 > cy2)
                    count++;
            } else if (isPointOnLine(cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y)) {
                if (cy2 > cy1)
                    count++;
            } else if (isIntersect(cx1, cy1, cx2, cy2, linePoint1x, linePoint1y, linePoint2x, linePoint2y)) {
                count++;
            }
        }
        System.out.println(count);
        if (count % 2 == 1) {
            isInside = true;
        }

        return isInside;
    }


    public double Multiply(double px0, double py0, double px1, double py1, double px2, double py2) {
        return ((px1 - px0) * (py2 - py0) - (px2 - px0) * (py1 - py0));
    }


    public boolean isPointOnLine(double px0, double py0, double px1, double py1, double px2, double py2) {
        boolean flag = false;
        double ESP = 1e-9;
        if ((Math.abs(Multiply(px0, py0, px1, py1, px2, py2)) < ESP) && ((px0 - px1) * (px0 - px2) <= 0)
                && ((py0 - py1) * (py0 - py2) <= 0)) {
            flag = true;
        }
        return flag;
    }


    public boolean isIntersect(double px1, double py1, double px2, double py2, double px3, double py3, double px4,
                               double py4) {
        boolean flag = false;
        double d = (px2 - px1) * (py4 - py3) - (py2 - py1) * (px4 - px3);
        if (d != 0) {
            double r = ((py1 - py3) * (px4 - px3) - (px1 - px3) * (py4 - py3)) / d;
            double s = ((py1 - py3) * (px2 - px1) - (px1 - px3) * (py2 - py1)) / d;
            if ((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1)) {
                flag = true;
            }
        }
        return flag;
    }
}
